package graph;

import java.util.ArrayList;
import java.util.List;

/**
 * create by yongli on 2020-02-09 09:56
 * 选择一种图的存储结构，然后构造图对象。
 * 这个限定为一个int值，没有考虑到通用性.
 */

public abstract class Graph<T> {
    int V;
    int E;
    // 临接表,表示有向图 next
    List[] adj;

    Graph(){} // 继承者需要使用.

    Graph(int V) {
        adj = new ArrayList[V];
        for (int i = 0; i < V; ++i) {
            adj[i] = new ArrayList<Integer>();
        }
        this.V = V;
    }

    int V() {
        return V;
    }

    int E() {
        return E;
    }

    //添加v-->w
    abstract void addEdge(int v, int u);
    //返回v节点连接的路径
    abstract List<Integer> adj(int v);
    //s
    abstract List<Integer> search(int s);

    // 判断是否有边s-->w
    abstract boolean hasPathTo(int s, int w);

    // s-->w的路径,如果路径不只一种怎么办？
    abstract List<Integer> pathTo(int s, int w);

    @Override
    public String toString() {
        String s = "Graph[ V=" + V + "，E=" + E + "，]";
        for (int i = 0; i < V; ++i) {
            s += (V + ":");
            //表示V连接了哪些点
            for (int w : this.adj(i)) {
                s += w + " ";
            }
            s += "\n";
        }
        return s;
    }
}
